package com.jiang.剑指Offer.树.NC273;

import com.jiang.剑指Offer.树.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/10 21:42
 */
public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root2 == null || root1 == null) return false;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root1);
        while (!q.isEmpty()) {
            TreeNode node = q.poll();
            // 节点值等于root2的根节点值，进行判断
            if (node.val == root2.val) {
                if (dfs(node, root2)) return true;
            }
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        return false;

    }
    private boolean dfs(TreeNode node1, TreeNode node2) {
        if (node2 == null) return true;
        if (node1 == null) return false;

        if (node1.val == node2.val) {
            return dfs(node1.left, node2.left) && dfs(node1.right, node2.right);
        }

        return false;
    }
}
